#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>

// 函数声明
double power(int x, int k);
void reverse_string(char* str, int left, int right);
int my_strlen(char* str);
int digit_sum(unsigned int x);

/*
 * 主函数 - 演示递归算法的多种应用
 * 包括：幂运算、字符串反转、数字各位数求和
 */
int main()
{
    printf("=== 递归算法演示程序 ===\n\n");
    
    // 演示幂运算
    printf("1. 幂运算功能\n");
    int base, exponent;
    printf("请输入底数和指数: ");
    scanf("%d %d", &base, &exponent);
    double result = power(base, exponent);
    printf("%d 的 %d 次方 = %.3lf\n\n", base, exponent, result);
    
    // 演示字符串反转
    printf("2. 字符串反转功能\n");
    char arr[] = "abcdefg";
    printf("原字符串: %s\n", arr);
    int left = 0;
    int right = my_strlen(arr) - 1;
    reverse_string(arr, left, right);
    printf("反转后字符串: %s\n\n", arr);
    
    // 演示数字各位数求和
    printf("3. 数字各位数求和功能\n");
    unsigned int number = 0;
    printf("请输入一个正整数: ");
    scanf("%d", &number);
    int sum = digit_sum(number);
    printf("%d 的各位数字之和 = %d\n", number, sum);
    
    return 0;
}

/*
 * 计算x的k次方（递归实现）
 * 参数:
 *   x - 底数
 *   k - 指数（可为负数）
 * 返回值:
 *   x的k次方结果
 */
double power(int x, int k)
{
    // 指数大于0的情况：x^k = x * x^(k-1)
    if (k > 0)
    {
        return x * power(x, k - 1);
    }
    // 指数等于0的情况：任何数的0次方都等于1
    else if (k == 0)
    {
        return 1.0;
    }
    // 指数小于0的情况：x^(-k) = 1 / x^k
    else
    {
        return 1.0 / power(x, -k);
    }
}

/*
 * 计算字符串长度
 * 参数:
 *   str - 字符串指针
 * 返回值:
 *   字符串的长度（不包括结束符'\0'）
 */
int my_strlen(char* str)
{
    int count = 0;
    // 遍历字符串直到遇到结束符
    while (*str != '\0')
    {
        count++;
        str++;
    }
    return count;
}

/*
 * 使用递归方式反转字符串（双指针法）
 * 参数:
 *   str   - 字符串指针
 *   left  - 左边界索引
 *   right - 右边界索引
 */
void reverse_string(char* str, int left, int right)
{
    // 递归终止条件：当左边界大于等于右边界时停止
    if (left >= right)
    {
        return;
    }
    
    // 交换左右边界位置的字符
    char temp = *(str + left);
    *(str + left) = *(str + right);
    *(str + right) = temp;
    
    // 递归处理内部子字符串
    reverse_string(str, left + 1, right - 1);
}

/*
 * 计算正整数各位数字之和（递归实现）
 * 参数:
 *   x - 输入的正整数
 * 返回值:
 *   各位数字之和
 */
int digit_sum(unsigned int x)
{
    // 基础情况：如果只有一位数，直接返回该数
    if (x < 10) 
    {
        return x;
    }
    // 递归情况：最后一位数字 + 剩余数字的各位和
    else
    {
        return (x % 10) + digit_sum(x / 10);
    }
}